package com.example.demo.leetcode.zuocheng.graph;

/**
 *
 * 一个数组，A，B两个人拿，每个人只能从头尾拿，并且每个人都绝顶聪明，如果A先拿，问最后谁赢
 * 思路:
 *  定义先手函数 f(arr,L,R) 如果L==R 返回 arr[L], L!=R, 可能拿L,或者R， 递归后手两种子方案取最大值
 *  定义后手函数 s(arr,L,R) 如果L==R 返回0， L!=R， 递归先手子(L+1~R ,L~R-1)方案取最小值(因为对方必定会给你最小的值)
 *
 * @author xujm
 * @version V2.4
 * @since 2.4.0 2021/7/11 13:03
 */
public class Arr_从左往右范围模型 {

    public static void main(String[] args) {

        int [] arr ={4,6,7,8,9,11,2,34,52,3,6};
        int a = f(arr,0,arr.length-1);
        int b = s(arr,0,arr.length-1);
        System.out.println("a:"+a+"  b:"+b);

        System.out.println(dpway(arr));
    }


    public static int f(int [] arr,int L ,int R){
        if(L == R ){
            return arr[L];
        }
        int a = arr[L] + s(arr,L+1,R);
        int b = arr[R] + s(arr,L,R-1);
        return Math.max(a,b);
    }


    public static int s(int [] arr,int L,int R){
        if(L == R){
            return 0;
        }
        int a = f(arr,L+1,R);
        int b = f(arr,L,R-1);
        return Math.min(a,b);
    }

    /**
     * 动态规划: f 函数想象成一个正方形 n*n,
     *          s 函数想象成一个正方形 n*n,
     *          f依赖s填充正方形，s依赖f，
     *          最终结果存在于 dp[0][R] 中
     * @param arr
     * @return
     */
    public static int dpway(int [] arr){

        int n = arr.length;
        int [][] f = new int[n][n];
        int [][] s = new int[n][n];
        for(int i=0 ;i<n;i++){
            f[i][i] = arr[i];
        }

        for(int i=0;i<n;i++){
            int L = 0;
            int R = i+1;
            while(L <n && R < n ){

                f[L][R] = Math.max(arr[L]+s[L+1][R],arr[R]+s[L][R-1]);
                s[L][R] = Math.min(f[L+1][R],f[L][R-1]);
                L++;
                R++;
            }
        }
        return f[0][n-1];
    }




}
